You might have wished, after assessing 'S', instead of going to 'T' or 'Z', if we could have moved further beyond 'S' to 'F' and so on? That way, wouldn't be faster? This is what we will try here.
We will choose a neighbor, check if its goal, else choose its neighbor, and so on. We will first try few iterations and then get in to code as earlier. Just like earlier bag analogy we used in our BFS tree solution earlier,..
The very crux:¶
Just like BFS earlier, imagine we are at Arad (or node 'A').
Are we arleady at goal? No 'A' is not the goal. We need to make a move.
We have 3 options to choose from for our next move. S, T, Z. Why? Because those are the only cities/nodes connected to A. We will choose one. Say, we chose 'S'. After our first move, we will have again two choices 'RV', 'F'. And so on from first step.
Define our bag:
The peculiar characteristic is that, you cannot pick up at random any letter from the bag. What went last, comes out last. Last In First Out, LIFO). For example, in empty bag, if you had first put 'Z', followed by 'T', followed by 'S', then when you pick up one, it would be 'S'. Let us say, taking the letter from the bag is called popping.
Note this is unlike BFS, where it was FIFO. Also, like FIFO resembling a queue in computing, LIFO resembles a stack in computing. Now think how a stack works, and you could see the principle in play.
Disclaimer: I will also engage in a dirty trick here. When we feed the neighbors in to the bag, we will feed in reverse alphabetical order (for eg, instead of feeding S,T,Z, I will feed, Z,T,S, so next time when I pop, S comes out, making our solution faster in this particular case of reaching B)
Algorithm Development¶
Let us initialize as usual...hope you are now familiar with below constructs already from earlier sessions..
openSet = { 'A' }
closedSet = ( 'A' )
cameFrom[ 'A' ] = NoneCoding..
from collections import deque
from docHelpers_ipython import romania_location_map
cameFrom = { }
openSet = deque()
M = romania_location_map
start = 'A'
goal = 'B'
openSet.append(start)
cameFrom[start] = None
closedSet = set(start)
ITERATION 1
Is openSet empty? No. So Go on. Take first element from the openSet, in LIFO fashion: 'A' Is 'A' the goal? No. So Go on.
openSet : ( ) As 'A' is removed now neighbors : ( 'Z' , 'T', 'S' ) closedSet : ( 'A' ) None of neighbors in closed Set. So process all. openSet : ( 'Z' , 'T', 'S' ) closedSet : ( 'A', 'Z' , 'T', 'S' )Result: openSet = { ( 'Z' , 'T', 'S' ) }
Note:cameFromis not shown above as it could grow abnormally big to show here. Ok, I am lazy.
Coding..
if openSet:
current_node = openSet.pop() # NOTE THIS CHANGE. EARLIER POPLEFT. NOW FOR FIFO. TAKE FIRST ELEMENT
if current_node is not goal:
all_neighbors = reversed(M.get(current_node,[]).get('connections',[])) # TAKING IN REVERSE ORDER
for each_neighbor in all_neighbors: # add neighbors
if each_neighbor not in closedSet: # GRAPH: add to queue only if not already visited
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
list(openSet)
Visualizing..
from docHelpers_ipython import Doc
from IPython.core.display import HTML
doc = Doc(M)
resultHTML = doc.computeGraphs('A',['Z','T','S'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
ITERATION 2
Is openSet empty? No. So Go on. Take first element from the openSet, in LIFO fashion: 'S' Is 'S' the goal? No. So Go on.
openSet : ( 'Z' , 'T' ) As 'S' is removed now neighbors : ( 'O' , 'RV' ,'F' ) closedSet : ( 'A', 'Z' , 'T', 'S' ) None of neighbors in closed Set. Process all. openSet : ( 'Z' , 'T', 'O', 'RV', 'F' ) closedSet : ( 'A', 'Z' , 'T', 'S', 'O', 'RV', 'F' )Result: openSet = { ( 'Z' , 'T', 'O', 'RV', 'F' ) }
if openSet:
current_node = openSet.pop() # NOTE THIS CHANGE. EARLIER POPLEFT. NOW FOR FIFO. TAKE FIRST ELEMENT
if current_node is not goal:
all_neighbors = reversed(M.get(current_node,[]).get('connections',[])) # TAKING IN REVERSE ORDER
for each_neighbor in all_neighbors: # add neighbors
if each_neighbor not in closedSet: # GRAPH: add to queue only if not already visited
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
list(openSet)
resultHTML = doc.computeGraphs('S',['O', 'RV', 'F'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
ITERATION 3
Is openSet empty? No. So Go on. Take first element from the openSet, in LIFO fashion: 'F' Is 'S' the goal? No. So Go on.
openSet : ( 'Z', 'T', 'O', 'RV' ) neighbors : ( 'B' ) closedSet : ( 'A', 'Z' , 'T', 'S', 'O', 'RV', 'F' ) 'B' is already not visited, so process openSet : ( 'Z' , 'T', 'O', 'RV', 'B' ) closedSet : ( 'A', 'Z' , 'T', 'S', 'O', 'RV', 'F', 'B' )Result: openSet = { ( 'Z' , 'T', 'O', 'RV', 'B' ) }
if openSet:
current_node = openSet.pop() # NOTE THIS CHANGE. EARLIER POPLEFT. NOW FOR FIFO. TAKE FIRST ELEMENT
if current_node is not goal:
all_neighbors = reversed(M.get(current_node,[]).get('connections',[])) # TAKING IN REVERSE ORDER
for each_neighbor in all_neighbors: # add neighbors
if each_neighbor not in closedSet: # GRAPH: add to queue only if not already visited
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
list(openSet)
resultHTML = doc.computeGraphs('F',['B'], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
ITERATION 4
Is openSet empty? No. So Go on. Take first element from the openSet, in LIFO fashion: 'B' Is 'B' the goal? Yes, Success!
openSet : ( 'Z', 'T', 'O', 'RV' )Result: openSet = { ( 'Z' , 'T', 'O', 'RV' ) }
if openSet:
current_node = openSet.pop() # NOTE THIS CHANGE. EARLIER POPLEFT. NOW FOR FIFO. TAKE FIRST ELEMENT
if current_node is goal:
print('Yes. Success.')
else:
all_neighbors = reversed(M.get(current_node,[]).get('connections',[])) # TAKING IN REVERSE ORDER
for each_neighbor in all_neighbors: # add neighbors
if each_neighbor not in closedSet: # GRAPH: add to queue only if not already visited
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
list(openSet)
resultHTML = doc.computeGraphs('B',[], mappy=True, tree=True, queue=True, HTML=True)
HTML(resultHTML)
We finished in 4 iterations, going deep. Note the green nodes in above diagram. This is thus called, Depth First Search. We take a neighbor, check and go after its neighbors first.
One might also notice, this could be disadvantageous. What if we happen to choose a wrong route? Then we would have gone depth in that route come back all the way and taking correct route, thus ending up longer time. Thus with infinite graphs, DFS may never finish also.
Food for thought. Try feeding alphabetically and see, how longer it takes.
Coding:¶
One might also have noticed, the only thing we had to change programmatically was, instead of openSet.popleft() we used openSet.pop(). Everything else was same as BFS. So we shall go ahead, wrap all in function, with this only change and check again.
from collections import deque
from docHelpers_ipython import romania_location_map
cameFrom = { }
def reconstructPath(current_node):
Path = [current_node]
while current_node is not None:
current_node = cameFrom[current_node]
Path.append(current_node)
return reversed(Path[:-1])
def DFS(start, goal):
# INITIALIZATION
openSet = deque()
openSet.append(start)
cameFrom[start] = None
closedSet = set(start)
# MAIN LOOP
while openSet:
current_node = openSet.pop() # ONLY CHANGE FOR DFS
if current_node is goal:
print('Success. Route from {} to {} found. Path: {}'.format(start,goal,list(reconstructPath(current_node))))
break
all_neighbors = reversed(M.get(current_node,[]).get('connections',[])) # OK, A HACK HERE (OPTIONAL)
for each_neighbor in all_neighbors:
if each_neighbor not in closedSet:
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
return 'No Goal found!'
M = romania_location_map
start = 'A'
goal = 'B'
result = DFS(start, goal)
# one more test
start = 'S'
goal = 'N'
result = DFS(start, goal)
Voila! We did it again. It worked. We just created a DFS algorithm also for graphs!
Visualization (Optional)¶
We will inject a small code to keep track of bag contents, nodes traversed for sake of visualization. And then render an animation to visualize how nodes were traversed to reach the goal.
from collections import deque
from docHelpers_ipython import Doc
# VISUALIZATION PURPOSE
from IPython.display import display, Image
cameFrom = { } # This has to be globally accessible for reconstructPath to
def reconstructPath(current_node):
Path = [current_node]
while current_node is not None:
current_node = cameFrom[current_node] # Now current node would become 'A'
Path.append(current_node)
return reversed(Path[:-1]) # trimming
def DFS(start, goal):
# INITIALIZATION
openSet = deque()
openSet.append(start)
cameFrom[start] = None
closedSet = set(start) # GRAPH: we never get to add 'start' in closed set once in main loop, so we do now!
# MAIN LOOP
while openSet: #eventual failure exit
current_node = openSet.pop() # FIFO
if current_node is goal: # successful exit
print('Success. Route from {} to {} found. Path: {}'.format(start,goal,list(reconstructPath(current_node))))
break
# VISUALIZATION PURPOSE
all_neighbors = reversed(M.get(current_node,[]).get('connections',[]))
considered_neighbors = list(set(all_neighbors) - set(closedSet)) # thank you: https://stackoverflow.com/questions/3462143/get-difference-between-two-lists
for each_neighbor in reversed(M.get(current_node,[]).get('connections',[])): # add neighbors
if each_neighbor not in closedSet: # GRAPH: add to queue only if not already visited
openSet.append(each_neighbor)
cameFrom[each_neighbor] = current_node
closedSet.add(each_neighbor)
# VISUALIZATION PURPOSE
_ = doc.computeGraphs(current_node, considered_neighbors)
# VISUALIZATION PURPOSE
_ = doc.computeGraphs(current_node, [])
return 'No Goal found!'
M = romania_location_map
start = 'A'
goal = 'B'
# VISUALIZATION PURPOSE - called here caz we use doc in ourSearchAlgo
doc = Doc(M)
result = DFS(start, goal)
# VISUALIZATION PURPOSE
images = doc.render()
display(Image(images[0]),Image(images[1]),Image(images[2]))
BFS vs DFS Visual Comparison:¶
Take a moment to compare the BFS and DFS traversal, we just finished.
BFS goes layer by layer, whereas DFS goes depth in one direction, come back, goes into another and so on.